#include <iostream>
#include <stack>
using namespace std;

//两个栈实现一个队列， 假定s1入栈，s2出栈

//思路1 入栈直接入s1, 出栈把s2当缓冲，s1的所有pop到s2, s2 pop出队，然后把s2的所有pop到s1
template <typename T>
class Queue1
{
public:
    Queue1(){
        input = &s1;
        output = &s2;
    };
    ~Queue1(){};
    
    void push(T data)
    {
        input->push(data);
		printf("push:%d\n", input->top());
    };

	void pop()
	{
		if(input->empty())
			return;
		
		int count = input->size();
		for (int i=0; i<count; i++)
		{
			T data = input->top();
			input->pop();
			output->push(data);

		}
		printf("pop:%d\n", output->top());
		output->pop();
		
		count = output->size();
		for (int i=0; i<count; i++)
		{
			T data = output->top();
			output->pop();
			input->push(data);
		}
	};

private:
    stack<T> s1;
    stack<T> s2;
    
    stack<T> *input;
    stack<T> *output;
};


template <typename T>
class Queue2
{
public:
    Queue2(){
        input = &s1;
        output = &s2;
    };
    ~Queue2(){};
    
    void push(T data)
    {
		if(input->empty() && !output->empty())
		{
			int count = output->size();
			for (int i=0; i<count; i++)
			{
				input->push(output->top());
				output->pop();
			}
			input->push(data);
		}
		else
		{
			input->push(data);
		}
		printf("push:%d\n", input->top());
    };

	void pop()
	{
		if (output->empty() && !input->empty())
		{
			int count = input->size();
			for (int i=0; i<count; i++)
			{
				output->push(input->top());
				input->pop();
			}
			printf("pop:%d\n", output->top());
			output->pop();
		}
		else
		{
			printf("pop:%d\n", output->top());
			output->pop();
		}
	};

private:
    stack<T> s1;
    stack<T> s2;
    
    stack<T> *input;
    stack<T> *output;
};


template <typename T>
class Queue3
{
public:
    Queue3(){
        input = &s1;
        output = &s2;
    };
    ~Queue3(){};
    
    void push(T data)
    {
		input->push(data);
		printf("push:%d\n", input->top());
    };

	void pop()
	{
		if (output->empty())
		{
			int count = input->size();
			for (int i=0; i<count; i++)
			{
				output->push(input->top());
				input->pop();
			}
			printf("pop:%d\n", output->top());
			output->pop();
		}
		else
		{
			printf("pop:%d\n", output->top());
			output->pop();
		}
	};
private:
    stack<T> s1;
    stack<T> s2;
    
    stack<T> *input;
    stack<T> *output;
};

int main(int argc, char* argv[])
{
	Queue3<int> queue;
	queue.push(1);
	queue.push(2);
	queue.push(3);
	queue.pop();
	queue.push(4);
	queue.push(5);
	queue.push(6);

	queue.pop();
	queue.pop();
	queue.pop();
	queue.pop();
	system("pause");
	return 0;
}